1. Field of the Invention
The present invention relates computer graphics. More specifically, one or more embodiments of the present invention relate to a rasterizer interpolator.
Portions of the disclosure of this patent document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever.
2. Background Art
Display images are made up of thousands of tiny dots, where each dot is one of thousands or millions of colors. These dots are known as picture elements, or “pixels”. A raster is a grid of x and y coordinates in a two dimensional display space, and in a three dimensional display space includes a “z” coordinate. A rasterizer is used to operate on pixels or sub-pixels within the raster grid in order to determine a final color values for the pixels. As will be further explained below, current rasterizers are inefficient. This problem can be better understood by reviewing an example of a graphics systems where a rasterizer might be used.
Graphics System
Each pixel in a raster environment has multiple attributes associated with it, including a color and a texture. The color of each pixel being represented by a number value stored in the computer system. A three dimensional display image, although displayed using a two dimensional array of pixels, may in fact be created by rendering of a plurality of graphical objects.
Examples of graphical objects include points, lines, polygons, and three dimensional solid objects. Points, lines, and polygons represent rendering “primitives” which are the basis for most tendering instructions. More complex structures, such as three dimensional objects, are formed from a combination or mesh of such primitives. To display a particular scene, the visible primitives associated with the scene are drawn individually by determining those pixels that fall within the edges of the primitive, and obtaining the attributes of the primitive that correspond to each of those pixels. The obtained attributes are used to determine the displayed color values of applicable pixels.
Sometimes, a three dimensional display image is formed from overlapping primitives or surfaces. A blending function based on an opacity value associated with each pixel of each primitive is used to blend the colors of overlapping surfaces or layers when the top surface is not completely opaque. The final displayed color of an individual pixel may thus be a blend of colors from multiple surfaces or layers.
In some cases, graphical data is rendered by executing instructions from an application that is drawing data to a display. During image rendering, three dimensional data is processed into a two dimensional image suitable for display. The three dimensional image data represents attributes such as color, opacity, texture, depth, and perspective information. The draw commands from a program drawing to the display may include, for example, X and Y coordinates for the vertices of the primitive, as well as some attribute parameters for the primitive (color and depth or “Z” data), and a drawing command. The execution of drawing commands to generate a display image is known as graphics processing.
Rasterizers
Graphics processing is typically performed with a rasterizer. A rasterizer receives pixels as input and may perform a scan conversion process on the pixels, apply textures to the pixels, apply color to the pixels, and shade the pixels by mathematically combining all of the results of the scanning, coloring, and texturing into a single final value for a pixel. This final value is typically output to a frame buffer which is configured to store the value temporarily and to provide it to the display device for drawing at the appropriate time.
The manner in which work is distributed to a rasterizer is currently inadequate. In particular, regions of a display screen are typically arranged into tiles. The tiles are used as a way to organize how and when a screen region of pixels will be passed to the rasterizer. One technique uses a rasterizer and arranges the screen into tiles. As geometric primitives are calculated and it is determined where the geometry falls on the screen, a determination is made as to which tiles have which portions of the geometry.
This is shown by example in FIG. 1. The screen 100 is divided into four tiles, tile 0, tile 1, tile 2, and tile 3. Geometry 110 (in this instance a triangle) is partially owned by tiles 0, 1, and 2. Rasterizer 120 receives the tiles (and hence the portions of the geometry) in order (i.e., tile 0, then tile 1, then tile 2). Problems occur, however, because this method is slow since it only rasterizers one tile at a time.
Another common rasterizer implementation uses elongated tiles such as that shown in FIG. 2. Elongated tile 200 has a 4×2 configuration. Narrow vertical line 210 (the geometry to be rendered) only passes through sub-tiles 220 and 230. However, this method has its problems because the tile size is not scaleable and, because of the elongated tile size, many empty tiles with no geometry are processed by the rasterizer, causing waste in time and computational power.
What is needed is a rasterization mechanism that is scaleable and efficient in minimizing wasted power spent on processing empty tiles.